The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

2(7(x1)) → 1(8(x1))
2(8(1(x1))) → 8(x1)
2(8(x1)) → 4(x1)
5(9(x1)) → 0(x1)
4(x1) → 5(2(3(x1)))
5(3(x1)) → 6(0(x1))
2(8(x1)) → 7(x1)
4(7(x1)) → 1(3(x1))
5(2(6(x1))) → 6(2(4(x1)))
9(7(x1)) → 7(5(x1))
7(2(x1)) → 4(x1)
7(0(x1)) → 9(3(x1))
6(9(x1)) → 9(x1)
9(5(9(x1))) → 5(7(x1))
4(x1) → 9(6(6(x1)))
9(x1) → 6(7(x1))
6(2(x1)) → 7(7(x1))
2(4(x1)) → 0(7(x1))
6(6(x1)) → 3(x1)
0(3(x1)) → 5(3(x1))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 3.
The certificate found is represented by the following graph.

Start state: 2949
Accept states: [2950, 2951, 2952, 2953, 2954, 2955, 2956]
Transitions:
2949→2950[2_1|0, 8_1|1, 4_1|1, 7_1|1]
2949→2951[5_1|0]
2949→2952[4_1|0]
2949→2953[9_1|0]
2949→2954[7_1|0]
2949→2955[6_1|0]
2949→2956[0_1|0]
2949→2949[1_1|0, 8_1|0, 3_1|0]
2949→2957[3_1|1]
2949→2959[6_1|1]
2949→2961[7_1|1]
2949→2962[0_1|1]
2949→2963[3_1|1]
2949→2964[3_1|2]
2949→2966[6_1|2]
2949→2960[3_1|2]
2949→2968[0_1|2]
2949→2967[3_1|3]
2957→2958[2_1|1]
2958→2952[5_1|1]
2959→2960[6_1|1]
2960→2952[9_1|1]
2960→2969[7_1|2]
2961→2953[6_1|1]
2962→2951[6_1|1]
2963→2956[5_1|1]
2963→2962[5_1|1]
2963→2968[5_1|1]
2964→2965[2_1|2]
2965→2950[5_1|2]
2966→2967[6_1|2]
2967→2950[9_1|2]
2967→2970[7_1|3]
2968→2956[6_1|2, 3_1|3]
2968→2962[6_1|2, 3_1|3]
2968→2968[6_1|2, 3_1|3]
2968→2951[3_1|2]
2969→2952[6_1|2]
2970→2950[6_1|3]

(2) BOUNDS(O(1), O(n^1))